1. Field of the Invention
This invention pertains to a system for designing a placement of a part in general, and more particularly to a system for designing a placement of a placement element, e.g., a cell, a terminal or a wire, in an integrated circuit, a printed circuit board or the like.
2. Description of the Related Arts
Placement elements, such as cells, terminals and wires in an integrated circuit, a printed circuit board or the like need to be placed, such that cells are integrated as highly as possible with the lowest possible routing cost.
A placement of placement elements has been determined by a comparison of the probability of a current placement with that of a new placement, in which routing costs based on the wire lengths or energies calculated by a simulated annealing method determine the probabilities.
Because a placement designing system such as that described above takes an increasing amount of time when placement elements increase in number, a faster system has been sought, as integrated circuits and printed circuit boards become more densely packaged.
The following are definitions of terms used in a forthcoming description.
A placement element: A placement element is an object to be placed in an integrated circuit, a printed circuit board or the like. Placement elements such as cells, terminals connected to a cell and wires are placed in an integrated circuit. Placement elements such as a placed cell and a via hole, which actually take up a part of a placement area, are placed in a printed circuit. A cell is defined as a single placement unit such as a single processor or a logic gate unit.
A placement area: A placement area is an area for placing placement elements, and is structured by placement element data on a placement element placed in an area, which are stored in a storage unit. A placement area is outputted, e.g., to a display as a printed circuit board or an integrated circuit board in which placement elements are placed.
A unit area: A unit area is obtained by splitting a placement area through an assignment of data (e.g., a unit area number) for specifying the unit area. For example, a unit area for a cell is ordinarily a basic cell (hereafter abbreviated as a BC), which is a form unit of a cell in a gate array, and a unit area for a wire is ordinarily a grid unit, where a grid is defined as the smallest unit of a VLSI (very large scale integrated circuit). One [1] cell may comprise a plurality of unit cells.
A virtual placement area: A virtual placement area for virtually placing a placement element is assigned to each type of a placement element in correspondence with data (e.g., a unit area number) for specifying a unit area for placing a placement element. The virtual placement area is structured by a storage unit for storing, e.g. attributes of a placement element, a proper name and a unit area number for making a placement. When a placement element is a cell, a terminal, a wire, or a via hole, a virtual placement area is called a cell area, a terminal area, a wire area or a via hole area.
A conventional placement designing system is such that a cell has data, e.g., on the position of a placement area when the placement of a circuit element of an integrated circuit is designed and that a terminal and a wire respectively have terminal data on connecting cells and wire data, thereby obtaining a placement of a cell and a wire connected to a cell.
FIG. 1 shows a conventional placement designing system.
In FIG. 1:
1 is a pointer storage unit for storing a pointer to placement element data (e.g., cell data, terminal data or wire data) on each type of placement element;
2 is a placement storage unit for storing placement element data (e.g., cell data, terminal data or wire data) on each type of placement element; and
3 is a placement area storage unit.
3' is a unit area split from a placement area in BC units, where each BC has a coordinate position expressed: e.g., in an x-y coordinate value;
4 is cell data on a cell having a cell number 1, which represents a placement element such as a logic gate in an integrated circuit;
5 is cell data on a cell having a cell number 2, which represents a placement element such as a logic gate in an integrated circuit;
6 is terminal data on a terminal having a terminal number A1, which connects the cell having cell number 1 to a wire having a wire number 1;
7 is terminal data on a terminal having a terminal number A2, which connects the cell having cell number 1 to a wire having a wire number 2;
8 is terminal data on a terminal having a terminal number A3, which connects the cell having cell number 2 to the wire having wire number 2 and a wire having a wire number 3;
9 is terminal data on a terminal having a terminal number A4, which connects the cell having cell number 2 to the wire having a wire number 3;
10 is wire data on the wire having wire number 1;
11 is wire data on the wire having wire number 2; and
12 is wire data on the wire having wire number 3.
Conventionally, the placement storage unit 2 has data storage areas respectively for cell data 4 (on the cell having cell number 1), cell data 5 (on the cell having cell number 2), terminal data 6 (on the cell having terminal number A1), terminal data 7 (on the terminal having terminal number A2), terminal data 8 (on the terminal having terminal number A3), terminal data 9 (on the terminal having terminal number A4), wire data 10 (on the wire having wire number 1), wire data 11 (on the wire having wire number 2) and wire data 12 (on the wire having wire number 3). Pointer storage unit 1 comprises pointers to data of respective placement elements.
The contents of the placement storage unit 2 and the placement area storage unit 3 are explained more concretely below. The placement area storage unit 3 stores coordinate positions of respective unit areas split from a placement area and characteristics of the unit areas, for example, a prohibition on a cell placement in a unit area. The placement storage unit 2, on the other hand, stores concrete data, e.g., on a cell and a terminal. For instance, the placement storage unit 2 stores the coordinate position of a unit area for placing a cell and the cell number of a cell connected to a terminal.
FIG. 2 shows a data structure of a conventional placement designing system.
More specifically, FIG. 2 shows an example of a placement and routing of a gate array. In FIG. 2:
13 is data representing a process of a gate array;
14 is a pointer to a placement element;
15 is what stores global data such as a temperature and dimensions of a placement area in an integrated circuit;
16 (corresponding to 1 shown in FIG. 1) is a pointer storage unit for storing pointers to data on respective placement elements, such as a pointer to cell data, a pointer to terminal data and a pointer to wire data;
17 is a cell area for storing in a sequence of cell numbers cell data such as coordinate positions of the unit areas at which cells (e.g. cell 4 (having cell number 1) and cell 5 (having cell number 2) shown in FIG. 1) are placed;
18 is a terminal area for storing in a sequence of terminal numbers terminal data such as cell numbers of cells to which terminals (e.g. terminal 6 (having terminal number A1), terminal 7 (having terminal number A2), terminal 8 (having terminal number A3), and terminal 9 (having terminal number A4) shown in FIG. 1) are connected and coordinate positions of unit areas at which the terminals are placed; and 19 is a wire area for storing in a sequence of wire numbers wire data such as terminal numbers of terminals to which wires (e.g. wire 10 (having wire number 1), wire 11 (having wire number 2) and wire 12 (having wire number 3)) are connected and coordinate positions of the unit areas at which wires are placed.
The temperature and dimensions of a placement area in an integrated circuit referred to here as global data are parameters for use in calculating routing costs based on the wire lengths or energies according to a simulated annealing method, which will be described later.
FIG. 1 looks as if the pointer to cell data points to cell 4 (having cell number 1) only and the pointer to terminal data points to terminal 6 (having terminal number A1) only. However, a pointer to cell data actually points to the head end of a cell area (e.g., a cell area 17 shown in FIG. 2) for storing cell data sequentially.
That is, the placement storage unit 2 shown in FIG. 1 is equivalent to a combination of the cell area 17, the terminal area 18 and the wire area 19 shown in FIG. 2.
Conventionally, a pointer to cell data specifies storage areas of data on respective cells and a pointer to terminal data specifies storage areas of data on respective terminals according to the data structure shown in FIG. 2. Based on the data in the storage areas specified by these pointers, a placement has been designed by placing cells at specified coordinate positions, by obtaining a cell connected to a terminal and by connecting a terminal to a specified cell.
A conventional placement designing system is explained below by using the coordinate positions of respective unit areas shown in FIG. 1.
Firstly, the pointer storage unit 1 specifies the pointer to cell data or the pointer to terminal data.
Secondly, according to the pointer to cell data, the pointer storage unit 1 sequentially specifies cell numbers 1, 2, etc., and writes into the cell area 17 cell data such as the coordinate positions (i.e. (1, 3) for cell 4 (having cell number 1) and (1, 4) for cell 5 (having cell number 2)) of the unit areas in the placement area at which cells 4 and 5 are placed.
Thirdly, according to the pointer to terminal data, the pointer storage unit 1 sequentially specifies cell numbers A1, A2, A3, A4, etc., and writes into the terminal area 18 terminal data such as the cell numbers (i.e. 1 for terminal 6 (having terminal number A1), 1 for terminal 7 (having terminal number A2), 2 for terminal 8 (having terminal number A3) and 2 for terminal 9 (having terminal number A4)) of the cells to which the terminals 6 through 9 are connected.
Fourthly, according to the pointer to wire data, the pointer storage unit 1 sequentially specifies wire numbers 1, 2, 3, etc., and writes into the wire area 19 wire data such as the terminal numbers (i.e., A1 for wire 10 (having wire number 1), A2 and A3 for wire 11 (having wire number 2) and A3 and A4 for wire 12 (having wire number 3)) of the terminals to which the wires 10, 11 and 12 are connected.
As well, although a placement area of an integrated circuit and a wire area of a printed circuit board may carry placement element data, the placement element data are limited, e.g., to data on cell dimensions, which do not include concrete data on a terminal or a wire between terminals.
More specifically, the placement element data were limited only to such data as on the number of cells classified by their dimensions placed in respective split areas.
FIG. 3 shows a method for changing a placement based on a conventional simulated annealing method.
A conventional placement change method is explained below according to the numbers shown in FIG. 3.
(1) New coordinate positions are created stochastically for placement elements such as a cell and a terminal. A random number, for example, is used for determining the new coordinate positions with a creation probability being uniform throughout a placement area.
(2) An energy difference before and after a placement change is calculated, where an energy is determined, e.g., by a wire length.
(3) By comparing the energy difference, an index as a benchmark for determining whether or not to move to a new coordinate position is created.
(4) An arbitrary number is generated as a random number, which is compared with the index calculated in (3), for determining whether or not to move to a new coordinate position. On positively determining a move to a new coordinate position, a placement is made at the new coordinate position. On negatively determining a move to a new coordinate position, a placement at a current coordinate position is maintained.
(1) through (4) are repeated until an optimal placement is obtained in (5) through a satisfaction of a terminating condition, thereby obtaining an optimal placement.
(5) The terminating condition is, for example, any one of (a) repetition a predetermined number of times, (b) a repetition until reaching less than a predetermined energy, and (c) a repetition until an energy reduction volume is less than a predetermined energy E at the end of N times where N is a predetermined number.
A conventional placement designing system stores placement elements in a sequence of cell numbers and in a sequence of terminal numbers, in which a cell has a coordinate position of a placement area (a position for placing a unit area), a terminal has a cell number of a cell for placing the terminal, and a wire has a terminal number to which the wire is connected. When a cell undergoes a placement change, after all cells are sequentially accessed for changing connection data (e.g., on a change of a cell coordinate value, a terminal connected to a cell and a wire connection), the cells and terminals are sequentially accessed for obtaining new placement data. Hence, a conventional placement designing system takes a large amount of time for processing a placement change. Also, because of the data structure, since the coordinate positions must be searched in the sequence of cell numbers and in the sequence of terminal numbers for a conversion to a new coordinate position in a placement change, the conventional method for designing a placement and a routing is not fit for a parallel computer incorporating a multiprocessor system.
Problems in changing a cell placement are explained in further detail below.
When a cell placement is changed, a critical point is that the changed cell has an overlap with another cell. To examine a cell overlap, there is a need to check, for each cell, whether a coordinate position after a cell movement is the same as a coordinate position before a cell movement.
When a cell is moved, terminal data need to be updated because the position of a terminal connected to the cell may be changed. When a cell does not have terminal data but instead a terminal has cell data as shown in FIGS. 1 and 2, all terminal data must be accessed for searching for a terminal connected to a cell.
When, for example, a position of the cell having cell number 1 is changed, a new coordinate position must be given to the cell having cell number 1. To examine whether a cell already exists at the new coordinate position, it must be checked whether the new coordinate position of the cell having cell number 1 is equal to the coordinate position of the cell having cell number 2 by accessing cell data on the cell having cell number 2. To search for all the terminals connected to the cell having cell number 1, it needs to be checked whether or not respective terminals (having terminal numbers A1, A2, A3 and A4) are connected to the cell having cell number 1 by accessing terminal data on these terminals (having terminal numbers A1, A2, A3 and A4). Accordingly, the processing for a change in a cell placement tends to require a greater amount of time.
When a placement element such as a cell corresponds with a placement area, a cell can have few data, which makes it difficult, if not impossible, to determine a placement satisfying a strict constraint (e.g., that a single cell is placed over a plurality of unit areas) dependent on a cell shape necessary in an actual placement or to evaluate the obtained placement under a strict constraint.
Also, conventionally, because the probability of creating a new coordinate value for changing a placement is uniform throughout a placement area, a movement destination is created unconditionally irrespective of cell characteristics. Hence, not only is efficiency low, but also processing takes too much time.